package graph;
import java.util.*;

/**
 * 邻接矩阵
 */
public class GraphByMatrix {
    private char[] arrayV;
    private int[][] matrix;
    private boolean isDirect;
    public GraphByMatrix(int size ,boolean isDirect) {
        arrayV = new char[size];
        matrix = new int[size][size];
        for (int i = 0; i < size; i++) {
            Arrays.fill(matrix[i],Constant.MAX);
        }
        this.isDirect = isDirect;
    }
    public void initArrayV(char[] array){
        for (int i = 0; i < arrayV.length; i++) {
            arrayV[i] = array[i];
        }
    }

    /**
     * 添加边
     */
    public void addEdge(char src,char dest,int weight){
        int srcIndex = findIndex(src);
        int destIndex = findIndex(dest);
       matrix[srcIndex][destIndex] = weight;
       //如果是无向图
        if(!isDirect){
            matrix[destIndex][srcIndex] = weight;
        }
    }
    public int findIndex(char v){
        for (int i = 0; i < arrayV.length; i++) {
            if(arrayV[i] == v){
                return i;
            }
        }
        return -1;
    }

    /**
     * 广度优先遍历
     * @param v
     */
   public void bfc(char v){
       int srcIndex = findIndex(v);
       Queue<Integer> queue = new LinkedList<>();
       queue.offer(srcIndex);
       boolean[] visited = new boolean[arrayV.length];
       while(!queue.isEmpty()) {
           Integer top = queue.poll();
           System.out.print(arrayV[top]+" ");
            visited[top] = true;
           //入队
           for (int i = 0; i < matrix[srcIndex].length ; i++) {
               if(matrix[top][i] != Constant.MAX
                       && visited[i] == false){
                   queue.offer(i);
                   visited[i] = true;
               }
           }
       }
   }
    /**
     * 深度优先遍历
     * @param v
     */
   public void dfs(char v){
       boolean[] visited = new boolean[arrayV.length];
       int srcIndex = findIndex(v);
       dfcChild(visited,srcIndex);
   }

    private void dfcChild(boolean[] visited, int srcIndex) {
        System.out.print(arrayV[srcIndex] + " ");
        visited[srcIndex] = true;
        for (int i = 0; i < arrayV.length; i++) {
            if(matrix[srcIndex][i]!=Constant.MAX
                    && visited[i] == false){
                dfcChild(visited,i);
            }
        }
    }

    public static void main(String[] args) {
        GraphByMatrix graph = new GraphByMatrix(4,true);
        char[] array = {'A','B','C','D'};
        graph.initArrayV(array);
        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);
        System.out.println("广度优先遍历:");
        graph.bfc('B');
        System.out.println();
        System.out.println("深度优先遍历:");
        graph.dfs('B');
    }
}
